#include "Heap.h"
#include <stdlib.h>

Heap *InitHeap(int size)
{
    Heap *newHeap = (Heap *)malloc(sizeof(Heap));
    newHeap->heapIdx = -1;
    newHeap->curLength = 0;
    newHeap->size = size;
    newHeap->heapArr = (ElementType *)malloc(sizeof(ElementType)*size);
}

void PushHeap(Heap *heap, ElementType newElement)
{
    if (heap->curLength < heap->size)
    {
        heap->heapArr[heap->curLength] = newElement;
        Swim(heap, heap->curLength);
        ++heap->curLength;
    }
}

ElementType PopHeap(Heap *heap)
{
    if (heap->curLength > 0)
    {
        ElementType topElem = heap->heapArr[0];
        heap->heapArr[0] = heap->heapArr[--heap->curLength];
        Sink(heap, 0);
        return topElem;
    }
    return NULL;
}

ElementType GetTop(Heap *heap)
{
    return heap->heapArr[0];
}

int FindElementIdx(Heap *heap, ElementType element)
{
    int length = heap->curLength;
    for (int i = 0; i < length; ++i)
    {
        if(heap->heapArr[i] == element)
        {
            return i;
        }
    }
    return -1;
}

void Clear(Heap *heap)
{
    heap->curLength = 0;
}

void Swim(Heap *heap, int index)
{
    int parent;
    while(index > 0)
    {
        parent = (index - 1) / 2;
        if(heap->cmpFunc(heap->heapArr[index], heap->heapArr[parent]))
        {
            Swap(&heap->heapArr[index], &heap->heapArr[parent]);
            index = parent;
        }
        else return;
    }
}

void Sink(Heap *heap, int index)
{
    int better, left = index * 2 + 1;
    int right;
    ElementType *heapArr = heap->heapArr;
    while (left < heap->curLength)
    {
        right = left + 1;
        better = right < heap->curLength && heap->cmpFunc(heapArr[right], heapArr[left]) ? right : left;
        if(heap->cmpFunc(heapArr[index], heapArr[better]))
        {
            return;
        }
        Swap(&heapArr[better], &heapArr[index]);
        index = better;
        left = index * 2 + 1;
    }
}

void Swap(ElementType *a, ElementType *b)
{
    ElementType tp = *a;
    *a = *b;
    *b = tp;
}